package com.demo.图;

import com.demo.图.model.Edge;
import com.demo.图.model.Graph;
import com.demo.图.model.Vertex;

import java.util.*;

/**
 * 迪克斯拉算法
 * @author cl
 */
public class GraphDijkstra {

    /** 求指定节点到其它节点的最短路径 */
    @SuppressWarnings("all")
    public static <T> Map<Vertex<T>, Integer> dijkstra(Graph<T> graph, Vertex<T> startNode) {
        Objects.requireNonNull(graph);
        Objects.requireNonNull(startNode);
        Map<Vertex<T>, Integer> result = new HashMap<>(16);
        // null 代表无穷大  可以用自定义堆提升性能
        HashSet<Vertex<T>> readyNode = new HashSet<>(graph.vertexMap.values());
        // 被选中的节点
        Vertex<T> selectedNode = startNode;
        while (selectedNode != null) {
            // 挪出已经选中的节点
            readyNode.remove(selectedNode);
            // 选中的节点影响的是它的下个节点们 计算并更新路径信息
            if (selectedNode == startNode) {
                result.put(selectedNode, 0);
            }
            for (Edge<T> next : selectedNode.edges) {
                // startNode -> selectedNode -> next 是否小于 startNode -> next
                if (result.get(next.to) == null || result.get(selectedNode) + next.weight < result.get(next.to)) {
                    result.put(next.to, result.get(selectedNode) + next.weight);
                }
            }
            // 挑选下一个节点 这个要是大小堆  那就自动排行序喽
            selectedNode = null;
            for (Vertex<T> node : readyNode) {
                if (result.get(node) == null) {
                    // 不可到的点
                    continue;
                }
                if (selectedNode == null || result.get(node) < result.get(selectedNode)) {
                    selectedNode = node;
                }
            }
        }
        return result;
    }
}
